//
// Created by hcDarren on 2018/8/25.
//

#ifndef NDK_DAY37_AS_ARRAYSTACK_H
#define NDK_DAY37_AS_ARRAYSTACK_H

#include <malloc.h>
#include <assert.h>

// 用数组来实现  （java Stack源码）
template<class E>
class ArrayStack {
private:
    // 栈顶元素的角标位置
    int top = -1;
    E *array = NULL;
    // 栈的初始长度
    int size = 10;

public:
    // 构造方法和析构方法
    ArrayStack();

    ~ArrayStack();

public:
    /**
     * 栈是否为空
     */
    bool isEmpty();

    /**
     * 弹出栈顶的元素
     */
    E pop();

    /**
     * 获取栈顶的元素但不弹出
     * @return
     */
    E peek();

    /**
     * 将元素压入栈中
     */
    void push(E e);

private:
    void growArray();
};

template<class E>
ArrayStack<E>::ArrayStack() { // 构造函数
    array = (E *) malloc(sizeof(E) * size);
}

template<class E>
ArrayStack<E>::~ArrayStack() { // 析构函数
    delete[] array;
}

template<class E>
E ArrayStack<E>::pop() {
    assert(top >= 0); // 断言，判断边界。是否越界了。<0时 抛异常。
    return array[top--];
}

template<class E>
bool ArrayStack<E>::isEmpty() {
    return top == -1;
}

template<class E>
E ArrayStack<E>::peek() { // 获取栈顶的元素但不弹出
    assert(top >= 0);
    return array[top];
}

template<class E>
void ArrayStack<E>::push(E e) { // 将元素压入栈中
    // 是否有足够的空间
    if (top + 1 == size) {
        // 扩容: 空间不够了。
        growArray();
    }
    array[++top] = e;
}

template<class E>
void ArrayStack<E>::growArray() { // 扩容
    // ArrayList 多带大家操作指针
    size += size >> 1;
    array = (E *) realloc(array, size * sizeof(E)); // 原来的基础上，扩容1/2。通常在后面开辟空间。
}

#endif //NDK_DAY37_AS_ARRAYSTACK_H
